package com.justonw.solution;


import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 从n个数中找出前k小元素
 */
public class Solution2 {

    /**
     * 方法一，基于大顶堆进行排序：大顶堆，保持堆顶元素为当前堆中元素的最大值
     * 时间复杂度为O(nlogk)
     *
     * 具体思路：
     * 第一步，创建一个大小为k的数据容器来存储最小的k个数，接下来，每次从输入的n个整数中读入一个数
     * 第二步，如果容器已有的数小于k，则直接把这次读入的整数放入容器中。
     * 第三步，如果容器中的已经有k个数了，容器已满。此时不能再插入新的数字，而需要替换已有的数。
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargeest(int[] nums, int k) {
        // 利用最大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        for (int i = 0; i < nums.length; i++) {
            if (maxHeap.size() != k) {
                maxHeap.offer(nums[i]);
            } else if (maxHeap.peek() > nums[i]) {
                //如果当前值比堆顶元素大，进入下一次循环
                //如果当前值比堆顶元素小，则将堆顶元素移出，然后将当前值插入到堆中并进行堆化
                maxHeap.poll();
                maxHeap.offer(nums[i]);
            }
        }
        return maxHeap.peek();
    }

    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int kthLargeest = solution2.findKthLargeest(new int[]{5, 6, 10, 7, 2, 10}, 3);
        System.out.println(kthLargeest);
    }



}
